//动态规划优化
//dynamic_programming_optimization.cpp

//本文简单的介绍一些流行的动态规划的优化方法
//本章中介绍的四类主要动态规划问题都是无差别的遍历所有决策空间
//但遍历的过程中还存在一些特殊的优化方法，使得算法在时间或空间上可以进一步的优化

//1)四边形不等式原理
//对于这样的一类状态转移方程：
//f[i][j] = | min(f[i][k-1] + f[k][j] + weight[i][j])	i < j, i < k <= j
//			| 0											i = j
//			| INF										i > j
//比如本章第3节的最小合并代价问题就符合这类状态转移方程
//假如对于i <= i' < j <= j'，有weight[i'][j] <= weight[i][j']
//则称函数weight具有关于区间包含的单调性
//另外假如有weight[i][j] + weight[i'][j'] <= weight[i'][j] + weight[i][j']
//则称函数weight满足四边形不等式
//
//在动态规划的求解中应用四边形不等式原理的条件
//在循环中当函数weight[i][j]的下标i和j超过某一临界值时
//可以跳过这个区域的循环，直接进行下一轮的决策遍历，从而达到减少时间复杂度的效果
//
//更多资料请参考“动态规划加速原理之四边形不等式”，作者“赵爽(华中师大一附中)”
//
//2)状态压缩
//状态压缩可以应用于很多问题，只要问题中每个成员的状态可以用二进制来表示
//比如一个4*4方格的棋盘，每个格子中可以摆放黑棋或白棋
//则棋盘的状态可以用一个16位的二进制数字来表示
//则可以使用short型变量，short型变量长度为2字节(byte)，16比特(bit)
//若问题中有32个可以用二进制的0和1表示状态的成员
//则可以使用int型变量，int型变量长度为4字节(byte)，32比特(bit)
//按照这样的思路推广，我们还可以得到任意的状态都可以用二进制数位来进行压缩
//当问题中每个成员有两种状态时，可以用一位二进制数字的0和1来表示
//当问题中每个成员有三到四种状态时，可以用两位二进制数字来表示，以此类推
//
//更多资料请参考“状态压缩动态规划”，作者“godfrey90”
